package leetcode.ArrayAndString;

public class RemoveElement {


    public static int removeElement(int[] nums, int val) {
        if(nums.length==0){
            return 0;
        }

        if(nums.length==1){
            if(nums[0]==val){
                return 0;
            }else{
                return 1;
            }

        }
        int i=0;
        int j  = nums.length - 1;
        for (;i<=j;i++){
            while(nums[j]==val){
                j--;
                if(j<0){ //一路减到头，回报脚标越界
                    return 0;
                }
            }
            if(nums[i]==val&&i<j){
                swap(nums,i,j);
                j--;
            }
        }
        return j+1;

    }

    //漂亮
    // 时间复杂度：O(n)
    // 假设数组总共有 n 个元素，i 和 j 至少遍历 2n 步。
    public static int betterRemoveElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
    //更漂亮的解法 效率更高
    //时间复杂度：O(n)，i 和 n 最多遍历 n 步。
    // 在这个方法中，赋值操作的次数等于要删除的元素的数量。
    // 因此，如果要移除的元素很少，效率会更高。
    public int betterRemoveElement2(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                // reduce array size by one
                n--;
            } else {
                i++;
            }
        }
        return n;
    }


    private static void swap(int[] ch, int i, int j) {
        int temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,2,3};

        System.out.println(betterRemoveElement(nums, 3)+"---");
        for(int a:nums){
            System.out.println(a);

        }
    }
}
